package lc216;
//找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
//
// 说明：
//
//
// 所有数字都是正整数。
// 解集不能包含重复的组合。
//
//
// 示例 1:
//
// 输入: k = 3, n = 7
//输出: [[1,2,4]]
//
//
// 示例 2:
//
// 输入: k = 3, n = 9
//输出: [[1,2,6], [1,3,5], [2,3,4]]
//
// Related Topics 数组 回溯 👍 373 👎 0

import java.util.ArrayList;
import java.util.List;

/**
 * 216. 组合总和 III
 * <a href="https://leetcode-cn.com/problems/combination-sum-iii/"/>
 * time:O(n!)  n等于k
 * space:O(1)
 * spend:15m
 */
class Solution {

    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        backTracking(1, k, n, path, ans);
        return ans;
    }

    private void backTracking(int start, int k, int n, List<Integer> path, List<List<Integer>> ans) {
        if(k == 0 && n == 0){
            ans.add(new ArrayList<>(path));
        }
        // 不满足的情况 k先剪到0，但是n没有等于0
        if(k == 0 || n == 0){
            return;
        }
        for(int i = start; i <= 9; i++){
            path.add(i);
            backTracking(i + 1, k - 1, n - i, path, ans);
            path.remove(path.size() - 1);
        }
    }

}
